
package com.liwt.algorithm;

/**
 * @desc 最大字段和问题。
 * @author 立刻bamboo
 * @create 2013-10-14
 * @see http://www.cnblogs.com/xibaohe/p/3361697.html ,
 *      http://hi.baidu.com/macrofuns/item/21fc130ed6570adf72e67643
 */
public class MaxSubArr {

    /**
     * 常规算法， 枚举
     * 
     * @param a
     * @return
     */
    private int maxSubArr1(int[] a) {
        int maxSub = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                int sumSofar = 0;
                for (int k = i; k <= j; k++) {
                    sumSofar += a[k]; // 计算 a[i]到a[j] 这个子段的和。
                }
                if (sumSofar > maxSub) {// 判断该子段和是否是当前最大的
                    maxSub = sumSofar;
                }
            }
        }
        return maxSub;
    }

    /**
     * 常规算法。枚举优化
     * 
     * @param a
     * @return
     */
    private int maxSubArr2(int[] a) {
        int sum[] = new int[a.length];
        sum[0] = a[0];
        for (int i = 1; i < a.length; i++) {
            sum[i] = sum[i - 1] + a[i];
        }

        int maxSub = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                int sumSofar = 0;
                // 计算 a[i]到a[j] 这个子段的和。
                if (i > 0) {
                    sumSofar = sum[j] - sum[i - 1];
                } else {
                    sumSofar = sum[j];
                }
                if (sumSofar > maxSub) {// 判断该子段和是否是当前最大的
                    maxSub = sumSofar;
                }

            }
        }
        return maxSub;
    }

    /**
     * 分治法
     * 
     * @param a
     * @param left
     * @param right
     * @return
     */
    private int maxSubArr3(int[] a, int left, int right) {
        if (left > right) {
            return 0;
        }
        int m = (left + right) / 2;
        if (left == right) { // 边际条件：当区间元素只有一个的时候返回自身
            return a[m];
        }
        if (right - left == 1) { // 边际条件：当区间元素只有两个的时候返回左、右、左右相加三者中的最大值
            return Math.max(Math.max(a[left], a[right]), a[left] + a[right]);
        }
        // 计算左区间的最大子段和。
        int Lmax = maxSubArr3(a, left, m);
        // 计算右区间的最大子段和
        int Rmax = maxSubArr3(a, m + 1, right);

        int CmaxL = Integer.MIN_VALUE, CmaxR = Integer.MIN_VALUE;
        int temp = 0;
        for (int i = m; i >= 0; i--) {// 左边找一个最大的和(必须包含端点 a[m])
            temp += a[i];
            if (temp > CmaxL) {
                CmaxL = temp;
            }
        }

        temp = 0;
        for (int i = m + 1; i <= right; i++) {// 右边找一个最大的和(必须包含端点 a[m+1])
            temp += a[i];
            if (temp > CmaxR) {
                CmaxR = temp;
            }
        }

        // 返回左区间的和、右区间的和、两者连起来的和中最大的
        return Math.max(Math.max(Lmax, Rmax), CmaxL + CmaxR);

    }

    /**
     * 动态规划算法
     * 
     * @param a
     * @return
     */
    private int maxSubArr4(int a[]) {
        int max = Integer.MIN_VALUE;
        int sum[] = new int[a.length];// 事实上，单独用一个变量 sumSofar就OK了。
        sum[0] = a[0];
        for (int i = 1; i < a.length; i++) {
            if (sum[i - 1] > 0) { // 如果第 i 个数后面一个数能构成的最大子段和大于 0
                sum[i] = sum[i - 1] + a[i]; // 大于就将第 i 个数加入其中
            } else {
                sum[i] = a[i]; // 否则第 i 个数自己组成一个最大子序列
            }
            if (sum[i] > max) {// 更新最大值
                max = sum[i];
            }
        }

        return max;
    }

    public static void main(String[] args) {
        // 待检测数组
        int[] arr = {
                -10, 5, 2, 3, 4, -5, -23, 3, 7, -21
        };
        MaxSubArr test = new MaxSubArr();
        int result = test.maxSubArr1(arr);
        System.out.println(result);

        result = test.maxSubArr2(arr);
        System.out.println(result);

        result = test.maxSubArr3(arr, 0, arr.length - 1);
        System.out.println(result);

        result = test.maxSubArr4(arr);
        System.out.println(result);
    }
}
